Nearest neighbour search is a simple technique widely usedin Pattern Recognition tasks. When the dataset is large and/or the dissimilarity computation is very time consuming the brute force approachis not practical. In such cases, some properties of the dissimilarity measure can be exploited in order to speed up the search. In particular, themetric properties of some dissimilarity measures have been used extensively in fast nearest neighbour search algorithms to avoid dissimilaritycomputations. Recently, a distance table based pruning rule to reducethe average number of distance computations in hierarchical search algorithms was proposed. In this work we show the effectiveness of thisrule compared to other state of the art algorithms. Moreover, we propose some guidelines to reduce the space complexity of the rule.
展开▼
